import java.util.Stack;

public class Solution84 {
    /**
     * 给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。
     */
    public int largestRectangleArea(int[] heights) {
        return dp(heights, 0, heights.length-1);
    }

    public int dp(int[] heights, int l, int r){
        if (l > r) return 0;
        int[] res = find(heights, l, r);
        int min = res[0];
        int index = res[1];
        int area = min * (r - l + 1);
        return Math.max(area, Math.max(dp(heights,l,index-1), dp(heights,index+1,r)));
    }

    public int[] find(int[] heights, int l, int r){
        int min = Integer.MAX_VALUE;
        int index = 0;
        for (int i = l; i <= r; i++) {
            if (heights[i] < min){
                min = heights[i];
                index = i;
            }
        }
        return new int[]{min, index};
    }


    // 单调栈
    public int largestRectangleArea2(int[] heights) {
        int ans = 0;
        Stack<Integer> stack = new Stack<>();
        stack.push(-1);
        for (int i = 0; i < heights.length; i++) {
            while (stack.peek() != -1 && heights[stack.peek()] >= heights[i]){
                ans = Math.max(ans, heights[stack.pop()] * (i - stack.peek() - 1));
            }
            stack.push(i);
        }
        while (stack.peek() != -1){
            ans = Math.max(ans, heights[stack.pop()] * (heights.length - stack.peek() - 1));
        }
        return ans;
    }
}
